package syf.rank;

import java.util.Arrays;

public class InsertRank {
    public static void main(String[] args) {
        int max=80000;
        int[] arr=new int[max];
        //8万个随机的数组排序
        for (int i=0;i<max;i++){
            arr[i]=(int)(Math.random()*100000);
        }
//        System.out.println(Arrays.toString(arr));
//        int[] arr={34,101,119,1};
        long now=System.currentTimeMillis();
        arr=insert(arr);
        long end=System.currentTimeMillis();
        System.out.println(end-now);//
    }
    /**
     * 插入排序（第一个元素认为是有序的，后面的都认为是无序的）
     * @param arr 要排序的数组
     * @return 排序好的数组
     */
    public static int[] insert(int[] arr){
        int insertVal;
        int insertIndex;
        for (int i=1;i<arr.length;i++){
            //这一次要插入的值
            insertVal=arr[i];
            //从有序列表的后面往前插入值，记录与之要比较的值的下标
            insertIndex=i-1;
            //当有序列表中的下标不为负数且
            while (insertIndex>=0&&insertVal < arr[insertIndex]){
                //把当前值往后移一位
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            //结束while后此时的 insertIndex+1即为要插入的位置
            arr[insertIndex+1]=insertVal;
        }
        return arr;
    }
}
/*        //第一个值已经放入到有序中
//        System.out.println(Arrays.toString(arr));
        for (int i=1;i<arr.length;i++){
            //待插入的值
            int insertVal=arr[i];
            //有序数组的下标
            int insertIndex=i-1;
            //当insertIndex下标大于0且即将插入的值小于有序数组的值时
            while (insertIndex>=0 && insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1]=insertVal;
//            System.out.println(Arrays.toString(arr));
        }
        return arr;*/